One edit distance

Time: O(M + N); Space: O(1)

Given two strings S and T, determine if they are both one edit distance apart.

One ediit distance means doing one of these operation:

  • insert one character in any position of S

  • delete one character in S

  • change one character in S to other character

Example 1:

Input: s = “aDb”, t = “adb”

Output: True

Example 2:

Input: s = “ab”, t = “ab”

Output: False

Explanation:

  • s=t ,so they aren’t one edit distance apart

[2]:

class Solution1(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        m, n = len(s), len(t)
        if m > n:
            return self.isOneEditDistance(t, s)
        if n - m > 1:
            return False

        i, shift = 0, n - m
        while i < m and s[i] == t[i]:
            i += 1
        if shift == 0:
            i += 1
        while i < m and s[i] == t[i + shift]:
            i += 1

        return i == m

[5]:

sol = Solution1()

s = "aDb"
t = "adb"
assert sol.isOneEditDistance(s, t) == True

s = "ab"
t = "ab"
assert sol.isOneEditDistance(s, t) == False

s = "teacher"
t = "acher"
assert sol.isOneEditDistance(s, t) == False